package divide;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 对于某些固定的 N，如果数组 A 是整数 1, 2, ..., N 组成的排列，使得：
 * 对于每个 i < j，都不存在 k 满足 i < k < j 使得 A[k] * 2 = A[i] + A[j]。
 * 那么数组 A 是漂亮数组。
 * 给定 N，返回任意漂亮数组 A（保证存在一个）。 
 * 示例 1：
 * 输入：4
 * 输出：[2,1,4,3]
 * 示例 2：
 * 输入：5
 * 输出：[3,1,2,5,4]
 * 提示：
 * 1 <= N <= 1000
 *
 *
 * 漂亮数组性质
 * （1）A是一个漂亮数组，如果对A中所有元素添加一个常数，那么Ａ还是一个漂亮数组。
 * （2）A是一个漂亮数组，如果对A中所有元素乘以一个常数，那么A还是一个漂亮数组。
 * （3）A是一个漂亮数组，如果删除一些A中一些元素，那么A还是一个漂亮数组。
 * （4) A是一个奇数构成的漂亮数组，B是一个偶数构成的漂亮数组，那么A+B也是一个漂亮数组
 * 比如:{1,5,3,7}+{2,6,4,8}={1,5,3,7,2,6,4,8}也是一个漂亮数组。
 * 因为  A[k] * 2 = A[i] + A[j] 在自身不成立
 * 如果 A[i] 是偶数部分 A[j] 是奇数部分   和一定是奇数  因此一定不成立
 *
 * 因此  思路是：
 * 1. 对于一个正整数 N, 我们将其等分为两部分，left和right，
 *      如果left部分是漂亮数组，right部分也是漂亮数组，
 *      同时left部分全部是奇数，right部分全部是偶数，
 *      那么此时left + right组成的数组一定也是一个漂亮数组。
 * 2. 对于从1到N的所有整数，奇数个数为 (N + 1) / 2，偶数个数为 N / 2
 * 3. 对于从1到(N + 1)/2的所有整数x，得出其漂亮数组，并映射成1到N范围的所有奇数 2 * x - 1
 * 4. 对于从1到N/2的所有整数x，得出其漂亮数组，并映射成1到N范围的所有偶数 2 * x
 *
 */
public class 漂亮数组_932 {
    Map<Integer, int[]> memory = new HashMap<>();

    // 法一： 记忆化递归
    public int[] beautifulArray(int n) {
        memory.put(1, new int[]{1});
        return f(n);
    }

    private int[] f(int n) {
        // 记忆化搜索  防止反复递归
        if(!memory.containsKey(n)) {
            int[] fn = new int[n];
            int idx = 0;
            for(int x : f((n+1)/2)) {
                fn[idx ++] = x * 2 -1;
            }
            for(int x : f(n/2)) {
                fn[idx ++] = x * 2;
            }
            memory.put(n, fn);
        }
        return memory.get(n);
    }


    // 法二： 分治   先分后治 ： 分了把结果合并起来
    //        这种会无限往下分  分到 123 这种  会导致重复无效递归
    int[] f1 = {1};
    int[] f2 = {1, 2};
    int[] f3 = {1, 3, 2};

    public int[] beautifulArray_divide(int n) {
        if(n == 1) return f1;
        if(n == 2) return f2;
        if(n == 3) return f3;
        int[] fn = new int[n];
        // 分
        int[] left = beautifulArray_divide((n+1)/2);
        int[] right = beautifulArray_divide(n/2);
        // 治
        System.arraycopy(left, 0, fn, 0, (n + 1)/2);
        System.arraycopy(right, 0, fn, (n + 1)/2, n/2);
        return fn;
    }



    // 法三： 分治 +   先分后治 ： 分了把结果合并起来
    //        这种会无限往下分  分到 123 这种  会导致重复无效递归
    Map<Integer, int[]> memory0 = new HashMap<>();
    {
        memory0.put(1, new int[]{1});
    }
    public int[] beautifulArray_divide_cache(int n) {
        if(!memory0.containsKey(n)) {
            int[] fn = new int[n];
            // 分
            int[] left = beautifulArray_divide_cache((n+1)/2);
            int[] right = beautifulArray_divide_cache(n/2);
            // 治
            for(int i = 0; i< left.length; i++) {
                fn[i] = left[i] * 2 - 1;
            }
            for(int i = 0; i< right.length; i++) {
                fn[i + (n+1)/2] = right[i] * 2 ;
            }
            memory0.put(n, fn);
            return fn;
        }
        return memory0.get(n);
    }

    public static void main(String[] args) {
        int[] ints = new 漂亮数组_932().beautifulArray_divide_cache(4);
        System.out.println( ints);
    }
}
